package com.breeze.sort;

/**
 * 归并排序-分治思想(D&C)
 * 1. 分解：将排序整个序列的问题分解为求解序列左右两侧的排序
 * 2. 求解：当序列分解只存在一个元素时即视为为有序
 * 3. 合并：合并两个分解的子序列使其成为新的有序序列，从而使整个序列有序
 */
public class MergeSort implements Sort {
    @Override
    public void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private void sort(int[] arr, int l, int r) {
        // 一个元素则为有序
        if (l >= r) {
            return;
        }
        int mid = (r + l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, mid, l, r);
    }

    private void merge(int[] arr, int mid, int l, int r) {
        // 临时数组保存原数组left到right的值
        int[] temp = new int[r - l + 1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = arr[l + i];
        }

        int i = l;
        int j = mid + 1;

        for (int k = l; k <= r; k++) {
            // i大于mid,说明mid左侧所有值已赋值完,接下来直接从右侧取值即可
            if (i > mid) {
                arr[k] = temp[j - l];
                j++;
                // j大于r，说明mid右侧所有值赋值完，直接从mid取值即可
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else {
                // 对mid两侧的最小值进行比较，取小的一方赋值
                if (temp[i - l] < temp[j - l]) {
                    arr[k] = temp[i - l];
                    i++;
                } else {
                    arr[k] = temp[j - l];
                    j++;
                }
            }
        }
    }
}
